package swardToOffer.struct_4_tree;

/**
 * @Author ChanZany
 * @Date 2021/5/26 10:59
 * @Version 1.0
 * 面试题55（二）：平衡二叉树
 * 题目：输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中
 * 任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
 * <p>
 * 方法1:分别计算左子树和右子树的深度,然后判断深度差值是否大于1
 * 方法2:后序遍历 + 剪枝 （从底至顶）
 * 思路是对二叉树做后序遍历，从底至顶返回子树深度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。
 * recur(root) 函数：
 * 返回值：
 * 当节点root左/右子树的深度差 ≤1 ：则返回当前子树的深度，即节点 root 的左/右子树的深度最大值 +1（ max(left, right) + 1 ）；
 * 当节点root左/右子树的深度差 >1 ：则返回−1 ，代表此子树不是平衡树 。
 */
public class BalancedBinaryTree {
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    private int recur(TreeNode root) {
        if (root == null) return 0;
        int left = recur(root.left);
        if (left == -1) return -1; //发现左子树不是平衡树,直接返回,停止递归
        int right = recur(root.right);
        if (right == -1) return -1; //发现右子树不是平衡树,直接返回,停止递归
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }


    public boolean isBalanced2(TreeNode root) {
        if (root == null) return true;
        int leftDepth = dfs(root.left);
        int rightDepth = dfs(root.right);
        //注意左子树和右子树也必须是平衡的才是平衡二叉树
        return Math.abs(leftDepth - rightDepth) <= 1 && isBalanced2(root.left) && isBalanced2(root.right);
    }

    private int dfs(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(dfs(root.left), dfs(root.right));
    }


}
